package main.Q701_800;

import java.util.*;

public class Q791_800 {
    public static void main(String[] args) {
        System.out.println("Question791：自定义字符串排序");
        System.out.println("Question792：匹配子序列的单词数");
        String[] strs=new String[]{"a","bb","acd","ace"};
        System.out.println(new Question792().numMatchingSubseq("abcde",strs));
        System.out.println("Question793：");
        System.out.println("Question794：");
        System.out.println("Question795：");
        System.out.println("Question796：旋转字符串");
        System.out.println("Question797：所有可能的路径");
        System.out.println("Question798：");
        System.out.println("Question799：");
        System.out.println("Question800：");
    }
}

class Question791 {
    public String customSortString(String order, String s) {
        StringBuffer result = new StringBuffer();
        char[] str = s.toCharArray(), strOrder = order.toCharArray();
        List<Character> list = new ArrayList<>();
        for (char c : str) list.add(c);
        for (char c : strOrder) {
            Character temp = c;
            while (list.contains(c)) {
                result.append(c);
                list.remove(temp);
            }
        }
        for (int i = 0; i < list.size(); i++) result.append(list.get(i));
        return result.toString();
    }
}

class Question792 {
    public int numMatchingSubseq(String s, String[] words) {
        int count = 0;
        Map<Character, TreeSet<Integer>> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            if (map.containsKey(s.charAt(i))) {
                map.get(s.charAt(i)).add(i);
            } else {
                TreeSet<Integer> index = new TreeSet<>();
                index.add(i);
                map.put(s.charAt(i), index);
            }
        }
        for (String word : words) {
            int lastIndex = -1;
            for (int i = 0; i < word.length(); i++) {
                if (map.containsKey(word.charAt(i))) {
                    TreeSet<Integer> indexs = map.get(word.charAt(i));
                    Integer higher = indexs.higher(lastIndex);
                    if (higher != null) {//存在相对顺序不变字符
                        lastIndex = higher;
                    }else {
                        break;
                    }
                } else {
                    break;
                }
                if (i == word.length() - 1) {//最后一个字符符合
                    count++;
                }
            }
        }
        return count;
    }
}

class Question796 {
    public boolean rotateString(String s, String goal) {
        if (s.length() > goal.length()) return false;
        String doubleString = s + s;
        return doubleString.contains(goal);
    }
}

class Question797 {
    List<List<Integer>> list = new ArrayList<>();

    public void process(int[][] graph, int start, List<Integer> lastList) {
        List<Integer> curList = new ArrayList<>(lastList);
        if (start == graph.length - 1) {//到达最后节点
            list.add(curList);
            return;
        }
        int[] cur = graph[start];
        for (int i = 0; i < cur.length; i++) {
            curList.add(cur[i]);//添加路径
            process(graph, cur[i], curList);//下一步路径
            curList.remove(curList.size() - 1);//撤销路径
        }
    }

    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<Integer> curList = new ArrayList<>();
        curList.add(0);//添加起点
        process(graph, 0, curList);
        return list;
    }
}